1. Field of the Invention
The invention relates to circuits for performing the S-transform, particularly VLSI implementations of such circuits.
2. Related Art
The S-transform is an image coding technique which is bit preserving, i.e. lossless. The transform is well suited for hierarchical image decomposition as well as image data compression. Hierarchical image decomposition is well suited for networks benefiting from progressive image transmission.
The S-transform has been described, inter alia, in Th. Wendler et al., "Proposed standard for variable format picture processing and a codec approach to match diverse imaging devices", SPIE vol. 318 (Part 1) Picture Archiving & Communications Systems (PACS) for Medical Applications (1982) pp.298-305.
An implementation of the S-transform in the context of coding images is given in U.S. Pat No. 4,134,134 (issued to Lux on Jan. 9, 1979).
Transforms applied to digital data are generally implemented using a conventional "butterfly" technique. In a butterfly technique, data is passed forward through a system, and processed in such a manner that the signal flow graphs for some data elements cross each other somewhat like a butterfly. A description of a butterfly technique, as applied to the FFT is given, for instance, in L. R. Rabiner et al., Theory and Application of Digital Signal Processing, (Prentice-Hall 1975) pp 361-363.
A disadvantage of the traditional techniques is that the circuit elements, such as adders and subtracters, are not used efficiently. Specifically, some of the elements are left idle while other elements are performing pieces of the transformation. The presence of idle circuit elements makes for expensive implementation in VLSI.